package com.mengfou.bitoperation;

/**
 * @author mengfou
 */
public class FindNumber {

    /**
     * 找到数组中出现次数为奇数的一个数，假定数组中其余数出现为偶次
     * @param arr 待查找数组
     * @return 下标
     */
    public int getNumber(int[] arr){
        if(arr == null || arr.length == 0) return -1;
        int res = arr[0];
        for (int i = 1; i < arr.length; i++) {
            res = res ^ arr[i];
        }
        return res;
    }


    /**
     * 假定数组中有两个数出现次数为奇数次，其余为偶数次。找出这两个数
     * @param arr 待查找数组
     * @return 下标数组
     */
    public int[] getTwoNumber(int[] arr){
        if(arr == null || arr.length == 0) return null;
        int res = arr[0];
        for (int i = 1; i < arr.length; i++) {
            res = res ^ arr[i];
        }

        // 提取出res二进制位中最右侧的1所代表的数
        int number = res & (~res + 1);

        int a = 0;
        for (int j : arr) {
            if ((number & j) == 0) {
                a = a ^ j;
            }
        }

        int b = res ^ a;
        return new int[]{a, b};
    }
}
